package com.itheima.leetcode.od.c.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * <h3>跳马问题</h3>
 */
public class BFSJumpingHorseProblem {
    public static int m;
    public static int n;
    public static int[][] matrix;
    public static int[][] result;
    public static int[][] directions = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        m = in.nextInt();
        n = in.nextInt();
        in.nextLine();
        result = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = 0;
            }
        }
        matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            String[] inputs = in.nextLine().split(" ");
            for (int j = 0; j < n; j++) {
                if (!inputs[j].equals(".")) {
                    clear_matrix();
                    bfs(i, j, Integer.parseInt(inputs[j]));
                    update_result();
                }
            }
        }

        int output = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (result[i][j] != -1) {
                    output = output > result[i][j] ? result[i][j] : output;
                } else {
                    continue;
                }
            }
        }
        if (output == Integer.MAX_VALUE) {
            System.out.println(0);
        } else {
            System.out.println(output);
        }
    }

    public static void clear_matrix() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = -1;
            }
        }
    }

    public static void update_result() {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == -1) {
                    result[i][j] = -1;
                } else if (result[i][j] == -1) {
                    result[i][j] = matrix[i][j];
                } else {
                    result[i][j] += matrix[i][j];
                }
            }
        }
    }

    public static void bfs(int i, int j, int step) {
        matrix[i][j] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        int index = 1;
        while (!queue.isEmpty() && index <= step) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] current = queue.poll();
                for (int l = 0; l < 8; l++) {
                    int next_i = current[0] + directions[l][0];
                    int next_j = current[1] + directions[l][1];
                    if (0 <= next_i && next_i < m && 0 <= next_j
                            && next_j < n && matrix[next_i][next_j] == -1) {

                        matrix[next_i][next_j] = index;
                        queue.add(new int[]{next_i, next_j});
                    }
                }

            }
            index += 1;
        }
    }
}